package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 1049. 最后一块石头的重量 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/26 11:10
 */
public class LastStoneWeightII {

    public static void main(String[] args) {
        LastStoneWeightII test = new LastStoneWeightII();

        // 1
//        int[] arr = {2,7,4,1,8,1};

        // 5
        int[] arr = {31, 26, 33, 21, 40};

        // 1
//        int[] arr = {23,29,16,44,4,40,15,22};

        // 1
//        int[] arr = {1,2};

        int i = test.lastStoneWeightII(arr);
        System.out.println(i);
    }


    public int lastStoneWeightII(int[] stones) {
        int a = stones.length;
        int f = stones[0];
        if (a == 1) {
            return f;
        }
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int b = sum >> 1;
        boolean[] arr = new boolean[b + 1];
        if (f <= b) {
            arr[f] = true;
        }
        for (int i = 1; i < a; i++) {
            int v = stones[i];
            if (v > b) {
                continue;
            }
            for (int j = b; j >= 0; j--) {
                if (arr[j] && j + v <= b) {
                    arr[j + v] = true;
                }
            }
            arr[v] = true;
        }
        for (int i = b; i > 0; i--) {
            if (arr[i]) {
                return sum - i - i;
            }
        }
        return b;
    }


    public int lastStoneWeightII2(int[] stones) {
        int a = stones.length;
        if (a == 1) {
            return stones[0];
        }
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int b = sum >> 1;
        int[][] arr = new int[a][b + 1];
        if (stones[0] <= b) {
            arr[0][stones[0]] = 1;
        }
        for (int i = 1; i < a; i++) {

            if (stones[i] > b) {
                continue;
            }
            int[] last = arr[i - 1];
            int[] item = arr[i];
            item[stones[i]] = 1;
            for (int j = 0; j <= b; j++) {
                if (last[j] == 1) {
                    item[j] = 1;
                    if (j + stones[i] <= b) {
                        item[j + stones[i]] = 1;
                    }
                }
            }
        }
        int[] item = arr[a - 1];
        for (int i = b; i > 0; i--) {
            if (item[i] == 1) {
                return sum - i - i;
            }
        }
        return b;
    }
}
